The present invention relates to an encoding apparatus, and more specifically to an error-correcting encoding apparatus.
Encoding technology is widely utilized in various fields. For example, in transmitting data, a source apparatus encodes data to be transmitted and sends the encoded data through a communications path so that a destination apparatus receives and decodes the encoded data. When data is stored in a storage device, it is encoded and written to a disk, etc. The encoded data is then decoded after being read from the disk. Encoding normally refers to converting a data sequence from an information source into a different data sequence, and thus the new data sequence obtained by the conversion is referred to as a code.
When encoded data is transmitted, an error may occur in the transmission path. An error may also occur when the encoded data is read for reproduction from a storage device that stores the encoded data. To detect an occurrence of such an error, or to correct such an error, an error-correcting code is frequently used.
A convolutional code is known as one type of error-correcting code. Each time n-bits of data is input for processing a convolutional code. Data of m (m>n) bits is then determined depending on the n-bit data and s-bit data, which is input immediately before the n-bit data is output. Thus, in processing the convolutional code, data of (m−n) bits is added for error correction to the data to be transmitted. As a result, the redundancy of the data is increased, thereby reducing the decoding error rate when the data is decoded.
The ratio of the amount of data to be transmitted (number of bits of source data) to the amount of data obtained by the encoding process (number of bits of output data) is commonly referred to as an encoding rate (or an information rate) R, and is represented by the following equation.R=n/m
The encoding rate R is always lower than 1 in an error-correcting code. Generally, the encoding rate R is one of the parameters for determining the error correction capability. For example, the lower the encoding rate R is, the higher the error correction capability becomes.
FIG. 20 is a block diagram showing an example of an existing error-correcting encoding apparatus using a convolutional code. The error-correcting encoding apparatus 500 includes two convolution units 501, 502 provided in parallel with each other. An encoding apparatus including plural convolution units connected in parallel with each other are often referred to as a “turbo-encoding apparatus”.
The error-correcting encoding apparatus 500 generates, for source data d, a data sequence x and parity data sequences y1,y2 for correcting the data sequence x. The data sequence x and the parity data sequences y1,y2 are then multiplexed and output. This output is the encoded data of the source data d. Described below is the operation performed when N-bits of source data d is encoded.
The source data d is output as the data sequence x as is, and is also transmitted to the convolution unit 501 and an interleaver 503. The convolution unit 501 performs a convolutional encoding process on the source data d and outputs the parity data sequence y1. The interleaver 503 temporarily stores the source data d and, then reads and outputs the stored source data in an order different from the input order. Thus, the source data d is randomized. The output from the interleaver 503 is then provided to the convolution unit 502. The convolution unit 502 also performs a convolutional encoding process on the output from the interleaver 503, and outputs the parity data sequence y2.
In the above described operations, the error-correcting encoding apparatus 500 generates an N-bit data sequence x, an N-bit parity data sequence y1, and an n-bit parity data sequence y2 for N-bits of source data d. The data sequence x and parity data sequences y1,y2 are, for example, multiplexed for each bit and output as the encoded data. Therefore, in this case, the error-correcting encoding apparatus 500 outputs 3×N bits of data for every N-bits input. As a result, the encoding rate R is ⅓.
FIG. 21 is a block diagram showing an example of a variation of the error-correcting encoding apparatus shown in FIG. 20. The error-correcting encoding apparatus 510 is realized by providing a selection unit 511 for the error-correcting encoding apparatus 500 shown in FIG. 20. According to a predetermined selection pattern, the selection unit 511 selects the parity data sequences y1, y2 respectively generated by the convolutional units 501, 502, and outputs it as a parity data sequence Z. The operation of the selection unit 511 is referred to as a “puncturing” process.
The selection unit 511 alternately selects one bit from the outputs of the convolution units 501, 502. Table 1 shows the output sequence Z produced by the selection unit 511. In Table 1, y1(i) indicates the output from the convolutional unit 501 corresponding to the i-th data element of the source data d, and y2 (i) indicates the output from the convolution unit 502 corresponding to the i-th data element of the source data d. When N-bits of source data d is input to the error-correcting encoding apparatus 510, the selection unit 511 outputs a N-bit output sequence Z (y1(1), y2(2), y1(3), y2(4), . . . , y1(N−1), y2(N)).
y1(1)y1(3). . . y1(N−1)y2(2)y2(4). . . y2(N)
The puncturing operation performed by the selection unit 511 is represented by the following equation.
                    Z        =                ⁢                  D          ·          P                                                       =                ⁢                                                            y1                ⁡                                  (                  i                  )                                                                                    y2                ⁡                                  (                  i                  )                                                                                                        y1                ⁡                                  (                                      i                    +                    1                                    )                                                                                    y2                ⁡                                  (                                      i                    +                    1                                    )                                                                                                ⁢                                            1                                      0                                                          0                                      1                                                                      ⁢                  (                                    i              =              1                        ,            3            ,            5            ,            …            ,                          N              -              1                                )                                   
The output sequence Z is obtained by multiplying the data matrix D by the puncturing matrix P. For example, for the i-th data element of the source data d, y1(i) is obtained by multiplying the first row of the data matrix D by the first column of the puncturing matrix P. For the (i+1) the data element of the source data d, y1(i+1) is obtained by multiplying the second row of the data matrix D by the second column of the puncturing matrix P. Therefore, the operation of the selection unit 511 for alternately selecting the outputs of the convolution units 501, 502 bit by bit is represented as an operation of repeatedly performing the above described arithmetic operations.
With the above described configuration, the error-correcting encoding apparatus 510 generates an N-bit data sequence x and an N-bit parity data sequence Z for N-bits of source data d. The data sequence x and the parity data sequence Z are multiplexed bit by bit, and then output as encoded data. Since the error-correcting encoding apparatus 510 outputs 2N bits of data for every N-bits input, the encoding rate R is ½.
U.S. Pat. No. 5,446,747 discloses in detail the above described error-correcting encoding apparatus shown in FIGS. 20 and 21.
In mobile terminal communications systems, it is required to optionally set the data length M of an output sequence from an encoding apparatus in relation to the data length N (number of bits) of source data d. For example, voice data, etc. is normally divided into data having a predetermined data length, and is then transmitted after being stored in a frame having a predetermined data length. Thus, when encoded data is processed in a mobile terminal communications system, voice data, etc. is divided into data having a predetermined data length, encoded and then stored in a frame.
However, the encoding rate R of the conventional error-correcting encoding apparatus shown in FIGS. 20 or 21 is fixed. Therefore, since the data has a predetermined fixed length (the frame in the above-described example), useless information has to be stored to fill the data storage area of the frame.
FIG. 22A shows the process for encoding source data using the error-correcting encoding apparatus 500 shown in FIG. 20 and storing the encoded data in a frame of a fixed length. In this example, the source data d occupies 333 bits, and the data storage area for a frame occupies 1500 bits. In this case, the error-correcting encoding apparatus 500 generates a 333-bit data sequence x, a 333-bit parity data sequence y1, and a 333-bit parity data sequence y2. Thus, to fill the data storage area of a frame, a 501-bit dummy data is required to be stored in the frame, as shown in FIG. 22B. If the frame is transmitted through a network, useless data is transmitted, thereby wasting network resources.
FIG. 23A shows the process of encoding source data using the error-correcting encoding apparatus 510 shown in FIG. 21 and storing the encoded data in a frame of a fixed length. In this example, the source data d occupies 666 bits, and the data storage area of a frame occupies 1500 bits. In this case, the selection unit 511 generates a parity data sequence Z from the parity data sequences y1, y2 in the puncturing process. Therefore, the error-correcting encoding apparatus 510 generates a 666-bit data sequence x, a 666-bit parity data sequence Z. As a result, to fill the data storage area of a frame, a 168-bit dummy data is stored in the frame as shown in FIG. 23B. Therefore, useless data is transmitted as shown in FIG. 22.
Thus, the encoding rate of the conventional error-correcting encoding apparatus having a plurality of convolution units provided in parallel with each other cannot be set to a desired value. Therefore, the source data is encoded and stored in a predetermined frame with poor efficiency.